/*
 * @lc app=leetcode.cn id=5 lang=javascript
 *
 * [5] 最长回文子串
 */

// @lc code=start
/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
  const n = s.length;
  //   标记从s[i...j]是否是回文串
  const isPalindrome = Array.from({ length: n }, () =>
    new Array(n).fill(false)
  );
  let maxLen = 1,
    start = 0;
  for (let j = 0; j < n; j++) {
    for (let i = 0; i < j; i++) {
      if (i === j) {
        isPalindrome[i][j] = true;
        continue;
      }
      if (s[i] === s[j]) {
        // 保证子串区间边界条件
        if (j - 1 - (i + 1) + 1 <= 1) {
          isPalindrome[i][j] = true;
        } else {
          isPalindrome[i][j] = isPalindrome[i + 1][j - 1];
        }
      }
      if (isPalindrome[i][j] && j - i + 1 > maxLen) {
        start = i;
        maxLen = j - i + 1;
      }
    }
  }
  return s.substring(start, start + maxLen);
};
// @lc code=end
